// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验(以 i,j 位置为结尾/开始......)，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界，结合多开数组的技巧
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 技巧：
// 使用滚动数组进行优化：删除横坐标，从右往左填表

// 例题 2：
// 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
//
//        示例 1：
//
//        输入：nums = [1,5,11,5]
//        输出：true
//        解释：数组可以分割成 [1, 5, 5] 和 [11] 。
//        示例 2：
//
//        输入：nums = [1,2,3,5]
//        输出：false
//        解释：数组不能分割成两个元素和相等的子集。
//
//
//        提示：
//
//        1 <= nums.length <= 200
//        1 <= nums[i] <= 100

// 解题思路:
// dp[i][j] 表示从 [0, i] 个数中选，能否凑成 sum / 2
// 初始化：
// 所有物品都不选：dp[i][0] = true
// 没有物品可以选：dp[0][j] = false
// 根据 i 物品选不选进行分析:
// 不选 i: dp[i][j] = dp[i - 1][j]
// 选 i: dp[i][j] = dp[i - 1][j - nums[i]]
// dp[i][j] = dp[i - 1][j] || (j >= nums[i] && dp[i - 1][j - nums[i]])

public class CanPartition {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int x : nums) sum += x;
        if(sum % 2 == 1) return false;

        int t = sum / 2;
        boolean[][] dp = new boolean[n + 1][t + 1];
        for(int i = 0; i <= n; i++){
            dp[i][0] = true;
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= t; j++){
                dp[i][j] = dp[i - 1][j] || (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]]);
            }
        }
        return dp[n][t];
    }
}
